package org.example;

import org.junit.jupiter.api.Test;

import javax.sql.rowset.BaseRowSet;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Divide
        implements INode {

    @Test
    void aa() {
        int[] preorder = {1, 2, 4, 5, 3, 6, 7};
        int[] inorder = {4, 2, 5, 1, 6, 3, 7};

        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);

        System.out.println(22);
    }

    private TreeNode dfs(int[] preorder,
                         Map<Integer, Integer> inorderMap,
                         int i,
                         int left,
                         int right) {
        if (left > right) {
            return null;
        }

        int nodeValue = preorder[i];
        TreeNode node = new TreeNode(nodeValue);
        Integer rootIdx = inorderMap.get(nodeValue);
        int leftRootIdx = i + 1;
        int leftLen = rootIdx - left;
        int rightRootIdx = leftRootIdx + leftLen;

        node.left = dfs(preorder, inorderMap, leftRootIdx, left, rootIdx - 1);
        node.right = dfs(preorder, inorderMap, rightRootIdx, rootIdx + 1, right);
        return node;

    }

    @Test
    void solveHanota() {
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();


    }

    void move(List<Integer> src,
              List<Integer> tar) {
        // 从 src 顶部拿出一个圆盘
        Integer pan = src.remove(src.size() - 1);
        // 将圆盘放入 tar 顶部
        tar.add(pan);
    }

    void dfs(int i,
             List<Integer> a,
             List<Integer> b,
             List<Integer> c) {
        if (i == 1) {
            move(a, c);
            return;
        }
        // 子问题 f(i-1) ：将 a 顶部 i-1 个圆盘借助 c 移到 b
        dfs(i - 1, a, c, b);
        move(a, c);
        // 子问题 f(i-1) ：将 b 顶部 i-1 个圆盘借助 a 移到 c
        dfs(i - 1, b, a, c);
    }
}
